package com.sunny.heap_putin;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * @Author zsunny
 * @Date 2018/9/23 10:41
 * @Mail zsunny@yeah.net
 */
public class Heap {

    ArrayList<Integer> sortRes = new ArrayList<>();
    ArrayList<Integer> heap = new ArrayList<>(Arrays.asList(-1));

    public static void main(String[] args) {

        int[] arr = {1,32,5,6,5,2,1,5,2,9};
        Heap heap = new Heap(arr);
        heap.insert(3);
        heap.heap.forEach(i->{
            System.out.print(i+" ");
        });
        System.out.println();
        heap.sort(heap.heap.size()-1);
        heap.sortRes.forEach(System.out::println);


    }

    public Heap(int[] arr) {
        for(int i=0; i<arr.length; i++){
            heap.add(arr[i]);
        }
        init(arr.length);
//        heap.forEach(i->{
//            System.out.print(i+" ");
//        });
//        System.out.println();
    }

    public void insert(int num){
        heap.add(num);
        int n = heap.size()-1;
        int cur = n>>1;
        while (cur >= 1){
            adjust(cur, n);
            cur >>= 1;
        }
    }

    public void adjust(int i, int n){
        int tmp = heap.get(i);
        int cur = i;
        int next = i<<1;
        while (next <= n){
            if(next + 1 <= n && heap.get(next+1) < heap.get(next)){
                next++;
            }
            if(heap.get(next) >= tmp){
                break;
            }
            heap.set(cur, heap.get(next));
            cur = next;
            next <<= 1;
        }
//        System.out.println(cur+"******"+tmp);
        heap.set(cur, tmp);
    }

    public void init(int n){
        int s = n>>1;
        for(int i=s; i>=1; i--){
            adjust(i, n);
        }
    }

    public void sort(int n){
        for(int i=1;i<=n;i++) {
            sortRes.add(heap.get(1));
//            System.out.println(heap.get(1)+" "+heap.get(n-i+1));
            Collections.swap(heap, 1, n-i+1);
//            heap.forEach(nn->{
//                System.out.print(nn+" ");
//            });
//            System.out.println();
            adjust(1, n-i);
//            heap.forEach(nn->{
//                System.out.print(nn+" ");
//            });
//            System.out.println();
        }
    }
}
